public class Solution {
    //链表中，倒数最后个K节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead==null){
            return pHead;
        }               //链表不为空
        ListNode temp = pHead;
        int count = 0;
        while(temp!=null){
            temp=temp.next;
            count++;
        }                   //判断链表有多长
        if(k>count){
            return null;
        }                   //倒数节点大于链表长度返回空
        count=count-k;
        while(count--!=0){
            pHead=pHead.next;
        }                   //走到对应位置
        return pHead;
    }


    //两个链表中的公共节点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;
        int count1 = 0;

        ListNode p2 = pHead2;
        int count2 = 0;

        while (p1 != null) {
            p1 = p1.next;
            count1++;
        }
        while (p2 != null) {
            p2=p2.next;
            count2++;
        }
        int lenDeff;
        ListNode longP,shortP;
        if(count1>=count2){                         //判断长的节点和短的节点
            lenDeff=count1-count2;
            longP=pHead1;
            shortP=pHead2;
        }else{
            lenDeff=count2-count1;
            longP=pHead2;
            shortP=pHead1;
        }
        while(lenDeff--!=0){                    //长的节点先走若干个，短的再走
            longP=longP.next;
        }
        while(longP!=null&&shortP!=null&&longP!=shortP){
            longP=longP.next;
            shortP=shortP.next;
        }
        return longP;
    }


    //两个链表中的公共节点   双指针法

    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;


        ListNode p2 = pHead2;


        while(pHead1!=pHead2){
            if(pHead1==null){
                pHead1=p2;
            }else{
                pHead1=pHead1.next;
            }

            if(pHead2==null){
                pHead2=p1;
            }else{
                pHead2=pHead2.next;
            }
        }

        return pHead1;

    }

    //反转链表
    private ListNode ReverseList (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;        //标记下一个点
            cur.next = head;            //插入头前面
            head = cur;                 //设置头
            cur = curNext;
        }
        return head;
    }

    //两个链表相加
    public ListNode addInList (ListNode l1, ListNode l2) {
        // write code here
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummyHead = new ListNode(0);

        ListNode newL1 = ReverseList(l1);       //反转两个链表

        ListNode newL2 = ReverseList(l2);

        ListNode head = dummyHead;

        int carry = 0;
        while(newL1!=null||newL2!=null||carry!=0){
            int sum = carry;
            if(newL1!=null){
                sum+=newL1.val;         //计算和
                newL1=newL1.next;
            }
            if(newL2!=null){
                sum+=newL2.val;
                newL2=newL2.next;
            }
            if(sum>=10){
                carry=sum/10;       //保存进位制
            }else{
                carry=0;
            }
            head.next=new ListNode(sum%10);
            head=head.next;
        }
        return ReverseList(dummyHead.next);     //反转回来
    }

    //反转局部链表
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if (head == null || head.next == null || m == n) {
            return head;
        }
        //将链表分成三个部分，m前 m-n n后
        //反转m-n之间的，最后再连接好
        ListNode dumyNode = new ListNode(0);
        dumyNode.next = head;
        ListNode prev = dumyNode;   //prev为m的前一个位置，防止从head位置反转，必须为定义的头链表开始
        //将prev走到m的前一个位置
        for (int i = 0; i < m-1; i++) {
            prev = prev.next;
        }
        System.out.println(prev.val);

        ListNode cur = head;
        //将cur走到n后一个位置
        for (int i = 1; i < n; i++) {
            cur = cur.next;     //现在时走到n的位置
        }
        System.out.println(cur.val);

        ListNode right = cur;   //记录下n的位置
        cur = cur.next;         //走到n后一个位置
        ListNode left = prev.next;  //标记m的位置

        prev.next = null;
        right.next = null;      //断开中间部分的连接，让后反转中间部分

        left = ReverseList(left);

        //反转后再进行连接
        prev.next=right;
        left.next=cur;


        return dumyNode.next;
    }
    //二分查找
    public int search (int[] nums, int target) {
        // write code here

        int length =  nums.length;
        int right = length-1;
        int left = 0;
        while(left<=right){
            int middle = (right+left)/2;
            if(nums[middle]>target){
                right=middle-1;
            }else if(nums[middle]<target){
                left=middle+1;
            }else{
                return middle;
            }

        }
        return -1;
    }
    //寻找数组中的峰值
    public int findPeakElement (int[] nums) {
        // write code here
        int length = nums.length;
        if (length == 1) {
            return 0;
        }
        for (int i = 1; i < nums.length ; i ++) {
            if (nums[i] < nums[i - 1]) {
                return i - 1;
            }
        }

        return nums.length - 1;
    }
}
